import java.util.*;

public class Solution103 {



    protected void processSubNode(List<Stack<TreeNode>> nodeStackList, TreeNode firstNode, TreeNode secondNode, Integer level){
        Stack<TreeNode> nodeStack = nodeStackList.get(level);
        if(Objects.nonNull(firstNode)){
            nodeStack.add(firstNode);
        }
        if(Objects.nonNull(secondNode)){
            nodeStack.add(secondNode);
        }
    }

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(Objects.isNull(root)){
            return res;
        }
        List<Stack<TreeNode>> nodeStackList = new ArrayList<>();
        Stack<TreeNode> firstStack = new Stack<>();
        firstStack.add(root);
        nodeStackList.add(firstStack);
        for (int level = 0; level < nodeStackList.size(); level++) {
            Stack<TreeNode> nodeQueue = nodeStackList.get(level);
            while(!nodeQueue.isEmpty()){
                TreeNode peekNode = nodeQueue.pop();
                int nextLevel = level + 1;
                TreeNode rightNode = peekNode.right, leftNode = peekNode.left;
                if(nodeStackList.size() == nextLevel){
                    nodeStackList.add(new Stack<>());
                }
                if(level % 2 == 1){
                    processSubNode(nodeStackList, rightNode, leftNode, nextLevel);
                } else {
                    processSubNode(nodeStackList, leftNode, rightNode, nextLevel);
                }
                if (res.size() == level) {
                    res.add(new ArrayList<>());
                }
                res.get(level).add(peekNode.val);
            }
        }
        return res;
    }


    public static void main(String[] args) {
        TreeNode treeNode = Solution1373.deserialize("1,2,3,4,null,null,5,null,null,null,null");
        Solution103 s = new Solution103();
        s.zigzagLevelOrder(treeNode);
    }
}
